package com.stable;

/**
 * 
 * @author Bhattacharjee, Bhatia
 * COP 5537, Network optimization
 * Project Code: Stable Marriage Program
 * 
 * 
 * This Class will generate Problem Matric for the Algorithm
 * 
 */
import java.util.*;

public class LocalSearchPG {

	private double p1 = 0.0;// probability for incompleteness
	private double p2 = 0.0;// probability for Ties

	// Number of men (=number of women)
	private int n;

	private Random rand = new Random();

	/**
	 * Creates and solves a random stable marriage problem of size n
	 */
	public static void main(String[] args) {
		if (args.length < 1) {
			System.out.println("Usage: java StableMarriage n");
			return;
		}
		int n = Integer.parseInt(args[0]);
		double p1 = Double.parseDouble(args[1]);
		double p2 = Double.parseDouble(args[2]);

		if (args.length == 3) {
			int[][] prefTableM = new int[n][n];
			int[][] prefTableW = new int[n][n];

			ArrayList<ArrayList<LinkedList<Integer>>> listM = new ArrayList<ArrayList<LinkedList<Integer>>>();
			ArrayList<ArrayList<LinkedList<Integer>>> listW = new ArrayList<ArrayList<LinkedList<Integer>>>();

			ArrayList<ArrayList<LinkedList<Integer>>> listM_T = new ArrayList<ArrayList<LinkedList<Integer>>>();
			ArrayList<ArrayList<LinkedList<Integer>>> listW_T = new ArrayList<ArrayList<LinkedList<Integer>>>();

			LocalSearchPG sm = new LocalSearchPG(n, p1, p2);
			prefTableM = sm.createRandomPreferenceList();
			prefTableW = sm.createRandomPreferenceList();

			sm.printPrefTables(prefTableM, true); // print Man preferences
			sm.printPrefTables(prefTableW, false); // print woman preferences

			// sm.printPrefTables();
			listM = sm.createIncompleteMaxtix(prefTableM);
			listW = sm.createIncompleteMaxtix(prefTableW);

			listM_T = sm.createTiePreflist(listM);
			listW_T = sm.createTiePreflist(listW);

			sm.printMatrixIT(listM_T, true);
			sm.printMatrixIT(listW_T, false);
		}

	}

	/**
	 * 
	 * @param M
	 *            True for man, False for woman
	 * @return create preference list for incomplete and Tie 
	 */

	
	public ArrayList<ArrayList<LinkedList<Integer>>> createPreferenceList_TI(boolean M) {

		int[][] prefTableM = new int[n][n];
		ArrayList<ArrayList<LinkedList<Integer>>> listM = new ArrayList<ArrayList<LinkedList<Integer>>>();
		ArrayList<ArrayList<LinkedList<Integer>>> listM_T = new ArrayList<ArrayList<LinkedList<Integer>>>();

		LocalSearchPG sm = new LocalSearchPG(n, p1, p2);
		prefTableM = sm.createRandomPreferenceList();

		sm.printPrefTables(prefTableM, M); // print Man preferences

		// sm.printPrefTables();
		listM = sm.createIncompleteMaxtix(prefTableM);

		listM_T = sm.createTiePreflist(listM);

		sm.printMatrixIT(listM_T, M);

		return listM_T;

	}

	/**
	 * Create a marriage problem with Incompleteness and Ties with size n with
	 * random preference and incompleteness probabilty p1 and Ties of
	 * probability p2
	 */

	public LocalSearchPG(int n, double p1, double p2) {
		this.n = n;
		this.p1 = p1;
		this.p2 = p2;
	}
	
	/**
	 * This function create Random preference List
	 * @return Random preferences
	 */

	public int[][] createRandomPreferenceList() {
		int[][] randomPref = new int[n][];

		for (int i = 0; i < n; i++) {
			randomPref[i] = new int[n];
			randomPref[i] = createRandomPrefs(randomPref[i]);

		}
		return randomPref;

	}

	/**
	 * create Incomplete Preference List from manPref or womanPref list
	 * 
	 * @param M
	 *            , True According to manPref and False according to womanPref
	 *            
	 *            create incomplete matrix of preferences.
	 */
	public ArrayList<ArrayList<LinkedList<Integer>>> createIncompleteMaxtix(
			int[][] prefMat) {
		// here now we perform incompleteness over problem
		int[][] pref = prefMat;
		ArrayList<ArrayList<LinkedList<Integer>>> listInComplete = new ArrayList<ArrayList<LinkedList<Integer>>>();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				double probe1 = rand.nextDouble();
				if ((probe1 <= p1)) {

					pref[i][j] = -1;

				}

			}
		}

		// return pref;

		// printPrefTables();
		for (int i = 0; i < n; i++) {

			ArrayList<LinkedList<Integer>> listInComplete1 = new ArrayList<LinkedList<Integer>>();
			for (int j = 0; j < n; j++) {
				if (pref[i][j] == -1) {
					continue;
				}
				LinkedList<Integer> linked1 = new LinkedList<Integer>();
				linked1.add(pref[i][j]);
				listInComplete1.add(linked1);
			}

			listInComplete.add(listInComplete1);

		}
		return listInComplete;

	}

	/**
	 * 
	 * @param listM
	 * @return create Ties over the incomplete matrix of preferences
	 */
	public ArrayList<ArrayList<LinkedList<Integer>>> createTiePreflist(
			ArrayList<ArrayList<LinkedList<Integer>>> listM) {
		// lsMPref
		// manPref
		ArrayList<ArrayList<LinkedList<Integer>>> listTief = new ArrayList<ArrayList<LinkedList<Integer>>>();

		for (int i = 0; i < n; i++) {

			ArrayList<LinkedList<Integer>> listTie = listM.get(i);
			for (int j = 0; j < listTie.size(); j++) {

				double probe1 = rand.nextDouble();
				if ((probe1 <= p2) && (j != 0)) {
					listTie = saveToPrevious(i, j, listTie);
				}

			}
			listTief.add(listTie);

		}

		return listTief;

	}

	private ArrayList<LinkedList<Integer>> saveToPrevious(int i, int j,
			ArrayList<LinkedList<Integer>> listTie) {

		LinkedList<Integer> linked1 = listTie.get(j - 1);
		if (linked1.isEmpty()) {
			saveToPrevious(i, j - 1, listTie);
		} else {
			listTie.get(j - 1).add(listTie.get(j).getFirst());
			listTie.remove(j);

		}

		return listTie;

	}

	/**
	 * Puts the numbers 0 .. v.length - 1 in the vector v in random order.
	 */
	private int[] createRandomPrefs(int[] v) {
		// Create a vector with the values 0, 1, 2, ...
		for (int i = 0; i < v.length; i++)
			v[i] = i;
		// Create a random permutation of this vector.
		for (int i = v.length - 1; i > 0; i--) {
			// swap v[i] with a random element v[j], j <= i.
			int j = rand.nextInt(i + 1);
			int temp = v[i];
			v[i] = v[j];
			v[j] = temp;
		}

		return v;

	}

	/**
	 * print the preference table 
	 * @param prefTable
	 * @param m, True for Man Pref, false for Woman pref
	 */
	public void printPrefTables(int[][] prefTable, boolean m) {
		if (m)
		System.out.println("manPref:");
		else
			System.out.println("WomanPref:");
		printMatrix(prefTable);

	}

	/**
	 * Prints the matrix v.
	 */
	private void printMatrix(int[][] v) {
		if (v == null) {
			System.out.println("<null>");
			return;
		}
		for (int i = 0; i < v.length; i++) {
			System.out.print(i + ": ");
			for (int j = 0; j < v[i].length; j++)
				System.out.print(v[i][j] + " ");
			System.out.println();
		}
	}

	/**
	 * Print the Matrix of Incomplete and Tie preferences.
	 * @param lsMPref2
	 * @param M, True for Man, False for Woman
	 */
	private void printMatrixIT(
			ArrayList<ArrayList<LinkedList<Integer>>> lsMPref2, boolean M) {

		if (M) {
			System.out.println("Man preference list with incompletes and Ties");
		} else {
			System.out
					.println("Woman preference list with incompletes and Ties");
		}

		if (lsMPref2 == null) {
			System.out.println("<null>");
			return;
		}
		for (int i = 0; i < lsMPref2.size(); i++) {
			System.out.print(i + ": ");
			for (int j = 0; j < lsMPref2.get(i).size(); j++) {
				System.out.print("(");
				for (int j2 = 0; j2 < lsMPref2.get(i).get(j).size(); j2++) {
					if (j2 == lsMPref2.get(i).get(j).size() - 1)
						System.out.print(lsMPref2.get(i).get(j).get(j2));
					else
						System.out.print(lsMPref2.get(i).get(j).get(j2) + " ");

				}
				System.out.print(") ");
			}
			System.out.println();
		}

	}

}
